package 热题100.普通数组.合并区间_56_中等;

import java.util.*;

/*
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

思路：
    之前的思路是将二维数组的两个一维数组拿出来比较，但是下次存入链表的时候无法对下一个数组进行处理，
    正解是二维数组的一个一维数组和链表中最后的一个数组比较来添加。

    nums.toArray(new int[nums.size()][]) nums是链表，存的是一个个数组，toArray方法将其转换为二维数组
* */
public class Solution {
    public static void main(String[] args) {
        int[][] intervals = {{1, 4}, {4, 5}};
        int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] ans = merge(intervals1);
        for (int[] p : ans) {
            for (int q : p) {
                System.out.print(q + " ");
            }
            System.out.println();
        }

    }

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0){
            return new int[0][2];
        }
        Arrays.sort(intervals, (Comparator.comparingInt(o -> o[0])));
        List<int[]> nums = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int l = intervals[i][0], r = intervals[i][1];
            // 如果nums没有添加元素或者最后一个元素的尾部 小于 数组元素的第一位，则直接添加到nums中
            if (nums.size() == 0 || nums.get(nums.size() - 1)[1] < l ) {
                nums.add(new int[]{l, r});
            } else {
                // 否则将数组最后一位更新成二者尾部的最大值
                nums.get(nums.size() - 1)[1] = Math.max(nums.get(nums.size() - 1)[1], r);
            }
        }
        return nums.toArray(new int[nums.size()][]);
    }
}